#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MaxSize 100
typedef char DataType;
typedef struct Node 
{
    DataType data;
    struct Node* lchild;
    struct Node* rchild;
}*BiTree,BitNode;
void CreateBitTree(BiTree *T);
void PreOrderTraverse(BiTree T); //先序遍历
void InOrderTraverse(BiTree T);
void PostOrderTraverse(BiTree T);
void InitBitTree(BiTree *T);
void DestroyBitTree(BiTree *T);
void LevelTraverse(BiTree T);
int main()
{
    freopen("in.txt","r",stdin);
    BiTree T;                                                       
    InitBitTree(&T);
    CreateBitTree(&T);
    PreOrderTraverse(T);
    printf("\n");
    InOrderTraverse(T);
    printf("\n");
    PostOrderTraverse(T);
    printf("\n");
    LevelTraverse(T);
    DestroyBitTree(&T);
    printf("\n");
}

void LevelTraverse(BiTree T)
{
    if(T)
    {
        BiTree queue[MaxSize];
        BiTree p;
        p = T;
        int front = -1;
        int rear = 0;
        queue[rear] = p;
        while (front != rear)
        {
            p = queue[++front];
            if(p->lchild) queue[++rear] = p->lchild;
            if(p->rchild) queue[++rear] = p->rchild;
            printf("%2c",p->data);
        }
    }
    
}
void CreateBitTree(BiTree *T)
{
    DataType ch;
    scanf("%c",&ch);
    if(ch == '#') *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BitNode));
        if(!(*T)) return;
        (*T)->data = ch;
        CreateBitTree(&((*T)->lchild));
        CreateBitTree(&((*T)->rchild));
    }
}

void PreOrderTraverse(BiTree T)
{
    /*if(T)
    {
        printf("%2c",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }*/
    BiTree stack[MaxSize];
    int top;
    BitNode *p;
    top = 0;
    p = T;
    while (p != NULL || top > 0)
    {
        while (p != NULL)
        {
            printf("%2c",p->data);
            stack[top++] = p;
            p = p->lchild;
        }
        while (p == NULL && top > 0)
        {
            p = stack[--top];
            p = p->rchild;
        }
    }
}

void InOrderTraverse(BiTree T)
{
    /*if(T)
    {
        InOrderTraverse(T->lchild);
        printf("%2c",T->data);
        InOrderTraverse(T->rchild);
    }*/
    BitNode *p;
    BiTree stack[MaxSize];
    int flag[MaxSize];
    int top1;
    top1 = 0;
    p = T;
    while (p != NULL || top1 > 0)
    {
        while(p != NULL)
        {
            stack[top1++] = p;
            p = p->lchild;
        }
        while (p == NULL && top1 > 0)
        {
            p = stack[--top1];
            printf("%2c",p->data);
            p = p->rchild;
        }
    }
}

void PostOrderTraverse(BiTree T)
{
    if(T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%2c",T->data);
    }
    //BitNode *p;
    //BiTree stack[MaxSize];
    //int flag[MaxSize];
    //int top1,top2;
    //top1 = 0;
    //top2 = 0;
    //p = T;
    //int temp;
    //while (p != NULL || top1 > 0)
    //{
    //    while (p != NULL)
    //    {
    //        stack[top1++] = p;
    //        flag[top2++] = 0;
    //        p = p->lchild;
    //    }
    //    while (p == NULL && top1 > 0)
    //    {
    //        p = stack[--top1];
    //        temp = flag[--top2];
    //        if(temp == 0)
    //        {
    //            stack[top1++] = p;
    //            flag[top2++] = 1;
    //            p = p->rchild;
    //        }
    //        else
    //        {
    //            printf("%2c",p->data);
    //            p = NULL;
    //        }
    //    }
    //}    
}

void InitBitTree(BiTree *T)
{
    (*T) = NULL;
}

void DestroyBitTree(BiTree *T)
{
    if(*T)
    {    
        DestroyBitTree(&((*T)->lchild));
        DestroyBitTree(&((*T)->rchild));
        free(*T);
        *T = NULL;
    }
}